'''
Created on Dec 20, 2011

@author: daan
@date_created: Dec 20, 2011 5:20:02 AM
'''
import math

class CarList(object):    
    def __init__(self):
        self._l = list()
        
    def AddFront(self, node):
        '''
        @param node: CarNode
        @return: CarNode 
        '''
        if 0 == self.Count():
            self._l.append(node)
        self._l.insert(0, node)
        
        return node
    
    def AddTail(self, node):
        '''
        @param node: CarNode
        @return: CarNode 
        '''
        self._l.append(node)
        
        return node
        
    def AddBefore(self, needle, node):
        '''
        @param node: CarNode
        @return: CarNode 
        '''
        i = self._l.index(needle)
        self._l.insert(i, node)
        
        return node
    
    def AddAfter(self, needle, node):
        '''
        @param node: CarNode
        @return: CarNode 
        '''
        i = self._l.index(needle)
        
        if (i + 1) < self.Count():
            self._l.insert(i + 1, node)
        else:
            self._l.append(node)
            
        return node
    
    def Remove(self, node):
        '''
        @param node: CarNode
        @return: CarNode 
        '''
        self._l.remove(node)
    
    def RemoveAll(self):
        self._l = list()
    
    def KeepMultiple(self, compare):
        self._l[:] = [x for x in self._l if compare(x)]
        
    def RemoveMultiple(self, compare):
        self._l[:] = [x for x in self._l if not compare(x)]
    
    def GetMultiple(self, compare):
        return [x for x in self._l if compare(x)]
    
    def GetNext(self, node):
        i = self._l.index(node)
        if (i + 1) < self.Count():
            return self._l[i + 1]
        return self._l[0]
    
    def GetPrev(self, node):
        i = self._l.index(node)
        if i > 0:
            return self._l[i - 1]
        return self._l[self.Count() - 1]
    
    def Count(self):
        return len(self._l)
    
    def Print(self):
        print self._l
        
    def GetList(self):
        return self._l
    
    def SearchNearby(self, location, size, lo=0, hi=None):
        if hi is None:
            hi = len(self._l)
        
        rng = size // 2
        
        while lo < hi:
            mi = (lo + hi) // 2
            
            midval = self._l[mi].b
            
            if midval < location - rng:
                lo = mi + 1
            elif midval > location + rng:
                hi = mi
            else:
                
                lo = 0 if lo < 0 else lo
                hi = len(self._l) - 1 if hi >= len(self._l) else hi
                
                return (self._l[lo], self._l[mi], self._l[hi], True)
            
        lo = 0 if lo < 0 else lo
        hi = 0 if hi < 0 else hi
        mi = 0 if mi < 0 else mi
        
        hi = len(self._l) - 1 if hi >= len(self._l) else hi
        lo = len(self._l) - 1 if lo >= len(self._l) else lo
        mi = len(self._l) - 1 if mi >= len(self._l) else mi
        
        try:
            return (self._l[lo], self._l[mi], self._l[hi], False)
        except:
            return -1
        
#        l = lambda x:-1 if x.b < (location - size) else 1 if x.b > (location + size) else 0
#    
#        return self._BinarySearch(l, 0 , self.Count() - 1)
    
    def _BinarySearch(self, compare, low=0, high=0):
        mid = (low + high) / 2
        if high < low:
            return (self._l[low], self._l[mid], self._l[high], False)
        
        comp = compare(self._l[mid])
        
        if comp > 0:
            return self._BinarySearch(compare, low, mid - 1)
        elif comp < 0:
            return self._BinarySearch(compare, mid + 1, high)
        else:
            return (self._l[low], self._l[mid], self._l[high], True)
